CD Ware Multimedia 1995 May/cd Ware (Juegos) Epimundo.iso/DOS/C/LLIST.ZIP/LISTLIST.C

C/C++ Source or Header | 1993-11-26 | 83.0 KB | 3,280 lines

/* ------------------------------------------------------------------------------
| FILE NAME: ListList.c
|
| DOCUMENT: [187.5]
|
| PURPOSE: To organize data of any type held anywhere in memory.
|
| KEY WORDS: DATA, LINKED LIST, SORT, SEARCH
|
| OVERVIEW: 'ListList' is an easy-to-use linked list manager.  It solves the
| general problem of how to handle odd pieces of data held anywhere in memory.
| Comes complete with a user's guide, source code for over 100 carefully
| explained procedures and a comprehensive test program.  Features a
| fast method for sorting long lists. Written in portable ANSI 'C'.
|
| Distributed on a Try-Before-You-Buy basis: price $5, see 'USAGE TERMS' below.
|
|------------------------------------------------------------------------------
|
| DESCRIPTION: 'ListList' is a system of routines for managing general-purpose
| linked lists.
|
| The form of lists in this system can be pictured as follows:
|
|                      [ListRecord]
|                           |
|                      [ItemRecord]<-->[ItemRecord]...
|                           |               |
|                         [Data]          [Data]
|
| Each list consists of two types of records: ListRecords and ItemRecords.
|
| The purpose of the ListRecord is to provide a fixed point of reference
| for accessing items contained in the list.
|
| The purpose of the ItemRecord is to associate items with one another and
| with the data they refer to.
|
| The purpose of the data is determined by your application.
|
| See 'ListList.h' for a detailed description of the fields contained
| in List and Item records.
|
| Usage is not limited to lists of strings: any kind of data located
| anywhere in memory can be itemized and manipulated via lists.
|
| Each procedure is explained in a comment header preceeding the source
| code for the procedure.
|
|------------------------------------------------------------------------------
|
| USAGE TERMS:
|
| This is commercial, for-profit software.  As the author, my terms are
| strict but easy to meet: you may use my software if you pay me $5 cash.
|
| This is a good deal for both of us: you gain by saving several weeks of
| your most precious resource and I gain by earning my living.
|
| Use of 'ListList' in software for profit or pleasure is encouraged.
| You may resell 'ListList' as part of your product without any
| limitations.  Feel free to edit the source to fit your style and add
| functions of your own.
|
| However, there is one usage restriction: use by government or non-profit
| organizations is prohibited.
|
| If you want to use ListList, the price is $5 cash with payment is due
| when you have saved more than $5 worth of your time by using it.
|
| Please mail cash payment to my permanent address:
|
|    LEE MALONE
|    1800 MARKET ST. #221
|    SAN FRANCISCO, CA  94102
|
| If you have more time than money, you can pay me in another way by
| helping to distribute my product.  Upload an unaltered copy of 'ListList.ZIP'
| to a new BBS or software library and you will have paid me in full.
|
| I value your business.  Comments welcome.
|
| Sincerely,
|
| Lee Malone
|
|------------------------------------------------------------------------------
|
| WARRANTY:  I take pride in the quality of my work and stand by it.
| I warrant this product to be free of errors and will gladly send a
| full refund and a correction if you find an error that I missed.
|
|------------------------------------------------------------------------------
|
| PACKING LIST:
|
| There are 9 files in the 'ListList' product:
|
|    ListList.DOC...ListList 5.0 User's Guide
|    Bytes.c........Byte manipulation procedures
|    Bytes.h........Byte library interface file
|    DataSize.h.....Compiler-specific definitions
|    ListList.c.....List manipulation procedures
|    ListList.h.....List library interface file
|    ListTest.c.....Test and example program
|    Strings.c......String manipulation procedures
|    Strings.h......String library interface file
|
| Shipped in compressed form as 'ListList.ZIP'.
|
|------------------------------------------------------------------------------
|
| GETTING STARTED: Running the Test Program
|
| 'ListList' has been fully tested and is free of errors, but you should
| compile and run the test program, 'ListTest.c', to make sure that it
| works properly with your compiler.  Some revision to the data types in
| file 'DataSize.h' may be required for your system.
|
|------------------------------------------------------------------------------
|
| HISTORY: 01.04.89 by Lee Malone
|          01.05.89 Completed writing Data Interface & Testing Operations
|          01.09.89 Completed writing Construction Operations
|          01.10.89 Moved from More to text file and compiled & tested.
|          01.11.89 Wrote & tested sort operations, wrote some test routines.
|          01.12.89 Added future enhancement documentation.
|          02.02.89 Added DeleteAllItemsFromAListThatMatchAAddressOfData
|          07.09.89 Upgraded lists to new format
|          07.19.89 Fixed errors in ExchangeItems, SortAscending, SortDescending
|          10.11.89 Deleted ItemNamePointer, ListNamePointer,
|                   and DataTypeID fields (to save space)
|          11.29.91 Ported to Focus Project.
|          10.25.93 Revised to conform to Focus usage.
|          10.26.93 The term 'node' replaced with 'item' for clarity.
|          11.22.93 Rev 5.0
|
|----------------------------------------------------------------------------- */

#include <ListList.h>

/* --------------------------- EQUATES ---------------------- */

/* You can set the size of the list stack with this equate. */
#define    MaxListStackItems    100

/* ------------------------- DATA ------------------------- */

AddressOfList        ListSpace;        /* Base address of list space.    */
AddressOfItem        ItemSpace;        /* Base address of item space.    */
Quad                 CountOfFreeLists; /* Lists available for use.       */
Quad                 CountOfFreeItems; /* Items available for use.       */
Quad                 MaxCountOfLists;  /* How many lists can exist.      */
Quad                 MaxCountOfItems;  /* How many items can exist.      */
AddressOfList        FirstFreeList;    /* 1st record in free list chain. */
AddressOfItem        FirstFreeItem;    /* 1st record in free item chain. */

AddressOfList        TheList; /* The current list. */
AddressOfItem        TheItem; /* The current item. */

Pair                 TheListSystemIsSetUp = 0;
                    /* A counter which is incremented
                     * each time the list system is
                     * set up, and decremented each
                     * time it is cleaned up.
                     * This allows multiple calls to
                     * set-up/clean-up procedures
                     * without causing problems.
                     */

Quad                 TheListStack[MaxListStackItems];
Quad                 TheListStackIndex;

Quad                 DirectAccessTableThreshold = 20;
                    /* Quantity of items, above which a         */
                    /* direct access table is used for sorting. */

/* --------------------- PROCEDURES ----------------------- */

/*------------------------------------------------------------
| NAME: BuildDirectAccessTableForList
|
| PURPOSE: To build a structure which permits direct access to
|          the items of a list.
|
| DESCRIPTION: Normally a linked list is accessed sequentially
| but there are some situations where direct access of items
| is needed. This procedure builds an index which can satisfy
| this requirement.
|
| A Direct Access Table is just an array of item record
| addresses.
|
| Direct access tables are dynamically allocated using
| 'AllocateMemory()'.
|
| The overall size of a direct access table depends on the
| number of items in the list that it is created from:
|
|      table size = ItemCount X sizeof(AddressOfItem)
|
| Use the 'FreeMemory()' procedure to discard useless
| direct access tables created by this procedure.
|
| See 'ReorderListToMatchDirectAccessTable()' to make the
| order of items in a list conform to the order in a
| cooresponding direct access table.
|
| EXAMPLE:
|           MyTable = BuildDirectAccessTableForList(MyList);
| NOTE:
|
| ASSUMES: Item pool has been set up.
|          Sufficient memory exists to hold the table.
|          At least one item exists in the given list.
|
| HISTORY: 09.12.89 by Lee Malone
|          10.03.91 Revised for Focus.
|                   Name changed from
|                   BuildARandomAccessTableForAList
|          12.22.91 pointers to data rather than pointers
|                   to items
|          02.08.93 name changed from
|                   BuildALinearAccessTableForAList
|          10.28.93 changed back to point to item records
|                   because mark field is part of data.
|          11.21.93 name changed from
|                   BuildLinearAccessTableForList
------------------------------------------------------------*/
AddressOfAddressOfItem
BuildDirectAccessTableForList(AddressOfList AList)
{
    AddressOfAddressOfItem    Table;
    Quad                    Entry;
    Quad                    TableSize;

    PushTheListAndItem();
    TheList = AList;

    TableSize = ((Quad) sizeof(AddressOfItem)) * TheItemCount;

    Table = (AddressOfAddressOfItem) AllocateMemory(TableSize);

    ToFirstItem();

    for( Entry = 0; Entry < TheItemCount; Entry++ )
    {
        Table[Entry] = TheItem;
        ToNextItem();
    }

    PullTheListAndItem();

    return(Table);
}

/*------------------------------------------------------------
| NAME: CleanUpTheListSystem
|
| PURPOSE: To reverse the action of SetUpTheListSystem.
|
| DESCRIPTION:
|
| EXAMPLE:  CleanUpTheListSystem();
|
| NOTE:
|
| ASSUMES: Any dynamic data attached to items has already
|          been deallocated.
|
| HISTORY: 03.10.89 by Lee Malone
|          07.10.89 upgraded to new structure
|          07.28.89 added set up flag
|          11.01.93 cleared the current list and item
------------------------------------------------------------*/
Nothing
CleanUpTheListSystem()
{
    if(!TheListSystemIsSetUp) return;

    TheListSystemIsSetUp--;
    if( !TheListSystemIsSetUp )
    {
        FreeMemory( ListSpace );
        FreeMemory( ItemSpace );

        TheList = 0;
        TheItem = 0;
        TheListStackIndex = 0;
        MaxCountOfLists  = 0;
        MaxCountOfItems  = 0;
        ListSpace        = 0;
        ItemSpace        = 0;
        CountOfFreeItems = 0;
        CountOfFreeLists = 0;
        FirstFreeList    = 0;
        FirstFreeItem    = 0;
    }
}

/*------------------------------------------------------------
| NAME: CreateItem
|
| PURPOSE: To make a new empty, unmarked, non-inserted item.
|
| DESCRIPTION:
|
| EXAMPLE:  AnItem = CreateItem();
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|          07.10.89 Revised for new item structure
|          11.17.93 simplified logic
|
------------------------------------------------------------*/
AddressOfItem
CreateItem()
{
    AddressOfItem AnItem;

    if(!IsItemCreationPossible())
    {
        printf("Error: Unable to CreateItem\n");
        exit(1);
    }

    CountOfFreeItems--;
    AnItem = FirstFreeItem;
    FirstFreeItem = GetNextItem(FirstFreeItem);
    UnMarkItem(AnItem);

    return( AnItem );
}

/*------------------------------------------------------------
| NAME: CreateItemForData
|
| PURPOSE: To make a new item and associate it with the given
|          data.
|
| DESCRIPTION: Construction operation.
|
| EXAMPLE:  AnItem = CreateItemForData( "Existence exists." );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 10.07.91 by Lee Malone
|          10.29.93 ported from Focus
|
------------------------------------------------------------*/
AddressOfItem
CreateItemForData( AddressOfByte SomeData )
{
    AddressOfItem ThisItem;

    ThisItem = CreateItem();
    PutItemDataAddress(ThisItem,SomeData);
    return(ThisItem);
}

/*------------------------------------------------------------
| NAME: CreateList
|
| PURPOSE: To make a new empty, unmarked list.
|
| DESCRIPTION:
|
| EXAMPLE:  AList = CreateList();
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|          07.10.89 new structure revision
|          11.17.93 simplified logic
|
------------------------------------------------------------*/
AddressOfList
CreateList()
{
    AddressOfList AList;

    if(!IsListCreationPossible())
    {
        printf("Error: Unable to Allocate List\n");
        exit(1);
    }

    CountOfFreeLists--;
    AList = FirstFreeList;
    FirstFreeList =
            (AddressOfList) GetFirstItemOfList(FirstFreeList);

    UnMarkList( AList );
    MarkListAsEmpty( AList );

    return(AList);
}

/*------------------------------------------------------------
| NAME: DeleteAllReferencesToData
|
| PURPOSE: To delete all items from a list that refer to the
|          given data address.
|
| DESCRIPTION:
|
| EXAMPLE:  DeleteAllReferencesToData( AList, SomeData);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.14.89 by Lee Malone
|          03.24.89 minor fixes
|          10.28.93 name changed from
|                   'DeleteAllItemsThatMatchData'
|          11.18.93 simplified logic
------------------------------------------------------------*/
Nothing
DeleteAllReferencesToData(AddressOfList AList,
                          AddressOfByte SomeData)
{
    AddressOfItem AnItem;

    PushTheListAndItem();
    TheList = AList;
    ToFirstItem();

    while( TheItem )
    {
        if(TheDataAddress == SomeData)
        {
            AnItem = ExtractTheItem();

            DeleteItem(AnItem);
        }
        else
        {
            ToNextItem();
        }
    }
    PullTheListAndItem();
}

/*------------------------------------------------------------
| NAME: DeleteFirstReferenceToData
|
| PURPOSE: To delete the first item in a list that refers to
|          the given data address.
|
| DESCRIPTION: Returns address of item that was deleted or
| a '0' if no matching item was found.
|
| EXAMPLE:  DeleteFirstReferenceToData( AList, SomeData);
|
| NOTE:
|
| ASSUMES: Data should not be freed using 'FreeMemory'.
|
| HISTORY: 12.12.91 by Lee Malone
|          10.29.93 name changed from
|                   'ExtractFirstMatchingData'
|
------------------------------------------------------------*/
AddressOfItem
DeleteFirstReferenceToData(AddressOfList AList,
                           AddressOfByte SomeData)
{
    AddressOfItem AnItem;

    AnItem = FindFirstItemLinkedToData( AList, SomeData);

    if( AnItem )
    {
        ExtractItemFromList(AList,AnItem);
        DeleteItem(AnItem);
    }
    return(AnItem);
}

/*------------------------------------------------------------
| NAME: DeleteItem
|
| PURPOSE: To discard an item that isn't part of a list.
|
| DESCRIPTION: Before an item can be deleted it must first
| be extracted from the list that holds it. Returns memory
| allocated from the item pool.
|
| EXAMPLE:  DeleteItem(AnItem);
|
| NOTE:
|
| ASSUMES: Item is not inserted in a list.
|
| HISTORY: 01.06.89 by Lee Malone
|          07.10.89 new structure revision
|
------------------------------------------------------------*/
Nothing
DeleteItem(AddressOfItem AnItem)
{
    CountOfFreeItems++;
    PutNextItem(AnItem,FirstFreeItem);
    FirstFreeItem = AnItem;
}

/*------------------------------------------------------------
| NAME: DeleteList
|
| PURPOSE: To delete items in a list and discard it.
|
| DESCRIPTION:
|
| EXAMPLE:  DeleteList(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.06.88 by Lee Malone
|          11.17.93 incorporated 'ReturnListToListPool'.
|
------------------------------------------------------------*/
Nothing
DeleteList(AddressOfList AList)
{
    AddressOfItem    AnItem;

    PushTheListAndItem();

    /* Make this the special list. */
    TheList = AList;

    /* Get rid of the items first. */
    while(IsAnyItemsInList(TheList))
    {
        ToFirstItem();

        AnItem = ExtractTheItem();

        DeleteItem(AnItem);
    }

    /* Then add the list record to the free list. */
    PutFirstItemOfList(AList,
                       (AddressOfItem) FirstFreeList);
    FirstFreeList = AList;
    CountOfFreeLists++;

    PullTheListAndItem();
}

/*------------------------------------------------------------
| NAME: DeleteListOfDynamicData
|
| PURPOSE: To delete a list of items and their associated
|          dynamically allocated data.
|
| DESCRIPTION: If all of the data in the given list has been
| created using 'AllocateMemory' then this procedure can be
| used to free the list and data in a single procedure call.
|
| EXAMPLE:  DeleteListOfDynamicData(AList);
|
| NOTE:
|
| ASSUMES: Every item data address points to a dynamicly
|          allocated segment of memory.
|
| HISTORY: 04.03.89 by Lee Malone
|          10.23.89 removed tree capability
|          10.03.91 Revised for Focus.
|                   Name changed from
|                   'DeleteListOfDynamicStrings'
|          11.18.93 changed to call 'DeleteList'.
------------------------------------------------------------*/
Nothing
DeleteListOfDynamicData(AddressOfList AList)
{
    PushTheListAndItem();

    /* make this the implied list */
    TheList = AList;

    ToFirstItem();
    /* Free the data attached to each item. */
    while(TheItem)
    {
        /* free the dynamic data */
        FreeMemory(TheDataAddress);
        ToNextItem();
    }

    /* Then free the list and item records. */
    DeleteList(AList);

    PullTheListAndItem();
}

/*------------------------------------------------------------
| NAME: DeleteMarkedItems
|
| PURPOSE: To delete all of the marked items in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  DeleteMarkedItems(AList);
|
| NOTE:
|
| ASSUMES: Data attached to item doesn't need to be
|          deallocated.
|
| HISTORY: 11.04.93 by Lee Malone
------------------------------------------------------------*/
Nothing
DeleteMarkedItems(AddressOfList AList)
{
    DeleteList( ExtractMarkedItems(AList) );
}

/*------------------------------------------------------------
| NAME: DuplicateList
|
| PURPOSE: To duplicate a list.
|
| DESCRIPTION: Creates a new list of item records pointing to
| the same data as the given list.
|
| This is useful when it is desirable to access the same data
| but in different orders or select different sets of data
| from the list using the marking bits in the mark field.
|
| EXAMPLE:  DupList = DuplicateList(AList);
|
| NOTE: Does NOT duplicate the data associated with the item
|       records.
|
| ASSUMES:
|
| HISTORY: 01.13.89 by Lee Malone
|          07.11.89 Added data type, mark and name copy
|          02.08.93 removed item count control in favor of
|                   TheItem being non-0.
|
------------------------------------------------------------*/
AddressOfList
DuplicateList(AddressOfList AList)
{
    AddressOfList DuplicateListAddress;
    AddressOfItem NewItem;

    PushTheListAndItem();

    DuplicateListAddress = CreateList();

    if(IsAnyItemsInList(AList))
    {
        TheList = AList;

        ToFirstItem();

        while(TheItem)
        {
            NewItem = CreateItemForData(TheDataAddress);
            PutItemMark(NewItem, TheItemMark);
            InsertItemLastInList(DuplicateListAddress,NewItem);
            ToNextItem();
        }
    }

    PullTheListAndItem();

    return(DuplicateListAddress);
}

/*------------------------------------------------------------
| NAME: DuplicateMarkedItems
|
| PURPOSE: To duplicate the marked items of a list.
|
| DESCRIPTION: Creates a new list of item records pointing to
| the same data as the marked items in the given list.
|
| This is useful when it is desirable to access the same data
| but in different orders or select different sets of data
| from the list using the marking bits in the mark field.
|
| EXAMPLE:  DupList = DuplicateMarkedItems(AList);
|
| NOTE: Does NOT duplicate the data associated with the item
|       records.
|
| ASSUMES:
|
| HISTORY: 11.04.93 by Lee Malone
|          11.19.93 simplified logic
|
------------------------------------------------------------*/
AddressOfList
DuplicateMarkedItems(AddressOfList AList)
{
    AddressOfList TheDuplicateList;
    AddressOfItem NewItem;

    TheDuplicateList = CreateList();

    if(!IsAnyItemsInList(AList)) return(TheDuplicateList);

    PushTheListAndItem();

    TheList = AList;

    ToFirstItem();

    while(TheItem)
    {
        if(IsItemMarked(TheItem))
        {
            NewItem = CreateItemForData(TheDataAddress);
            PutItemMark(NewItem, TheItemMark);
            InsertItemLastInList(TheDuplicateList,NewItem);
        }
        ToNextItem();
    }

    PullTheListAndItem();

    return(TheDuplicateList);
}

/*------------------------------------------------------------
| NAME: ExchangeItems
|
| PURPOSE: To exchange any two adjacent items in a given list.
|
| DESCRIPTION:
|
| EXAMPLE:  ExchangeItems(AList, AItem, BItem);
|
| NOTE:
|
| ASSUMES: Both items are valid item record addresses.
|          The items are next to one another.
|
| HISTORY: 01.09.89 by Lee Malone
|          07.10.89 revised to include type exchange
|          07.11.89 revised to include name and mark exchange
|          07.19.89 revised to exchange items, not just the
|                   data (latent error)
|
------------------------------------------------------------*/
Nothing
ExchangeItems(AddressOfList AList,
              AddressOfItem AItem,
              AddressOfItem BItem)
{
    AddressOfItem   WItem, XItem, YItem, ZItem;

    XItem = AItem;
    YItem = BItem;

    if( GetNextItem(XItem) != YItem )
    {
        XItem = BItem;
        YItem = AItem;
    }

    WItem = GetPriorItem(XItem);
    ZItem = GetNextItem(YItem);

    PutPriorItem(XItem,YItem);
    PutNextItem(YItem,XItem);
    PutPriorItem(YItem,WItem);
    PutNextItem(XItem,ZItem);

    if( WItem == 0 )             /* XItem was first */
    {
        PutFirstItemOfList(AList,YItem);
    }
    else
    {
        PutNextItem(WItem,YItem);
    }

    if( ZItem == 0 )             /* YItem was last */
    {
        PutLastItemOfList(AList,XItem);
    }
    else
    {
        PutPriorItem(ZItem,XItem);
    }
}

/*------------------------------------------------------------
| NAME: ExtractFirstItemFromList
|
| PURPOSE: To extract the first item from a list.
|
| DESCRIPTION:
|
| EXAMPLE:  AnItem = ExtractFirstItemFromList(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.06.88 by Lee Malone
|          07.10.89 simplified
|
------------------------------------------------------------*/
AddressOfItem
ExtractFirstItemFromList(AddressOfList AList)
{
    return(
        ExtractItemFromList(AList, GetFirstItemOfList(AList))
    );
}

/*------------------------------------------------------------
| NAME: ExtractItemFromList
|
| PURPOSE: To extract an item from a list.
|
| DESCRIPTION:
|
| EXAMPLE:  AnItem = ExtractItemFromList(AList, AnItem);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.06.88 by Lee Malone
|
------------------------------------------------------------*/
AddressOfItem
ExtractItemFromList(AddressOfList AList,
                    AddressOfItem AnItem)
{
    if( AnItem )
    {
        PushTheListAndItem();

        TheList = AList;
        TheItem = AnItem;

        AnItem = ExtractTheItem();

        PullTheListAndItem();
    }
    return(AnItem);
}

/*------------------------------------------------------------
| NAME: ExtractLastItemFromList
|
| PURPOSE: To extract the last item from a list.
|
| DESCRIPTION:
|
| EXAMPLE: AnItem = ExtractLastItemFromList(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.09.88 by Lee Malone
|          07.10.89 simplified
|
------------------------------------------------------------*/
AddressOfItem
ExtractLastItemFromList(AddressOfList AList)
{
    return(
        ExtractItemFromList(AList, GetLastItemOfList(AList))
    );
}

/*------------------------------------------------------------
| NAME: ExtractMarkedItems
|
| PURPOSE: To extract all marked items from a list and return
|          a list of those items.
|
| DESCRIPTION:
|
| EXAMPLE:  MarkedList = ExtractMarkedItems(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 11.04.93 by Lee Malone
|          11.19.93 simplified logic
------------------------------------------------------------*/
AddressOfList
ExtractMarkedItems(AddressOfList AList)
{
    AddressOfItem    AnItem;
    AddressOfList    ResultList;

    ResultList = CreateList();

    if(!IsAnyItemsInList(AList)) return(ResultList);

    PushTheListAndItem();

    TheList = AList;

    ToFirstItem();

    do
    {
        if(IsItemMarked(TheItem))
        {
            AnItem = ExtractTheItem();
            InsertItemLastInList(ResultList, AnItem);
        }
        else
        {
            ToNextItem();
        }
    }
    while( TheItem );

    PullTheListAndItem();

    return(ResultList);
}

/*------------------------------------------------------------
| NAME: ExtractTheItem
|
| PURPOSE: To extract the current item from the current list.
|
| DESCRIPTION:
|
| EXAMPLE:  AnItem = ExtractTheItem();
|
| NOTE:
|
| ASSUMES: Direction through list is first-to-last.
|
| HISTORY: 01.06.88 by Lee Malone
|          09.07.89 added 0 item protection
|          10.04.91 Revised for Focus.
|          11.26.91 revised to reset TheItem
|          12.01.91 IsItemAlone TheItem reset
|          10.25.93 removed MarkItemAsNotInserted
|          10.28.93 upgrade from Focus
|
------------------------------------------------------------*/
AddressOfItem
ExtractTheItem()
{
    AddressOfItem PrvItem;
    AddressOfItem NxtItem;
    AddressOfItem XItem;

    XItem = TheItem; /* The item being extracted */

    if(TheItem == 0) return(XItem);

    PrvItem = ThePriorItem;
    NxtItem = TheNextItem;

    TheItemCount--;

    if(IsItemAlone(TheItem))
    {
        MarkListAsEmpty(TheList);
        TheItem = 0;
    }
    else
    {
        if(IsItemFirst(TheItem))
        {
            /* mark next item as first  */
            MarkItemAsFirst(NxtItem);
            TheFirstItem = NxtItem;
            /* list now points to next item */
            ToFirstItem(); /* Reset TheItem */
        }
        else /* not the first item */
        {
            if(IsItemLast(TheItem))
            {
                /* mark previous item as last */
                MarkItemAsLast(PrvItem);
                TheLastItem = PrvItem;
                /* list now points to previous item */
                ToLastItem(); /* reset TheItem */
            }
            else /* somewhere in the middle */
            {
                /* relink neighboring items together */
                PutPriorItem(NxtItem,PrvItem);
                PutNextItem(PrvItem,NxtItem);
                TheItem = PrvItem; /* reset TheItem */
            }

        }
    }
    return(XItem);
}

/*------------------------------------------------------------
| NAME: FindFirstItemLinkedToData
|
| PURPOSE: To find the first item in a list pointing to the
| given data address.
|
| DESCRIPTION: Returns address of the item found, else 0.
|
| EXAMPLE:
|
|     AnItem = FindFirstItemLinkedToData(AList,SomeData);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 12.12.91 by Lee Malone
|          10.29.93 ported from procedure in Focus named,
|                     'FindFirstNodeMatchingData'
|          11.18.93 simplified logic
------------------------------------------------------------*/
AddressOfItem
FindFirstItemLinkedToData( AddressOfList AList,
                           AddressOfByte SomeData )
{
     AddressOfItem    Result;

    Result = (AddressOfItem) 0;

    /* Return if no items in the list. */
    if( !IsAnyItemsInList(AList) ) return(Result);

    PushTheListAndItem();

    TheList = AList;

    ToFirstItem();

    while( !IsItemLast(TheItem) )
    {
        if(TheDataAddress == SomeData) break;

        ToNextItem();
    }

    if( TheDataAddress == SomeData )
    {
        Result = TheItem;
     }

    PullTheListAndItem();

    return( Result );
}

/*------------------------------------------------------------
| NAME: FindFirstMarkedItem
|
| PURPOSE: To find the address of the first marked item in a
| list.
|
| DESCRIPTION:  Returns address of marked item or 0 if no
|               marked item was found.
|
| EXAMPLE:  AnItem = FindFirstMarkedItem(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 12.18.91 by Lee Malone
|          02.08.93 converted from list.txt
|          11.18.93 simplified logic
------------------------------------------------------------*/
AddressOfItem
FindFirstMarkedItem(AddressOfList AList)
{
    AddressOfItem    MarkedItem;

    PushTheListAndItem();

    TheList = AList;
    MarkedItem = (AddressOfItem) 0;

    ToFirstItem();

    while(TheItem)
    {
        if( IsItemMarked(TheItem) )
        {
            MarkedItem = TheItem;
            break;
        }
        ToNextItem();
    }

    PullTheListAndItem();

    return(MarkedItem);
}

/*------------------------------------------------------------
| NAME: FindFirstMatchingItem
|
| PURPOSE: To FindFirstMatchingItem.
|
| DESCRIPTION: Returns pointer to the item found, else 0
| Expects data field offset, width and address of value to
| match.
|
| EXAMPLE:
|
|  SearchValue          = (AddressOfByte) "John Galt";
|  SearchKeyFieldOffset = 0;
|  SearchFieldWidth        = CountString(SearchPattern);
|
|  MatchingItem = FindFirstMatchingItem( NameList,
|                                         SearchKeyFieldOffset,
|                                         SearchFieldWidth,
|                                         SearchValue );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 10.23.89 by Lee Malone
|          11.18.93 simplified logic
|
------------------------------------------------------------*/
AddressOfItem
FindFirstMatchingItem( AddressOfList AList,
                       Pair          FieldOffset,
                       Pair             FieldWidth,
                       AddressOfByte SearchValue )
{
     AddressOfItem    Result;

    Result = (AddressOfItem) 0;

    /* Return if no items in the list. */
    if( !IsAnyItemsInList(AList) ) return(Result);

    PushTheListAndItem();

    TheList = AList;

    ToFirstItem();

    while( !IsItemLast(TheItem)  )
    {
        if(IsTheDataMatching(FieldOffset, FieldWidth, SearchValue))
            break;
        ToNextItem();
    }

    if( IsTheDataMatching(FieldOffset, FieldWidth, SearchValue) )
    {
        Result = TheItem;
     }

    PullTheListAndItem();

    return( Result );
}

/*------------------------------------------------------------
| NAME: FindFirstUnMarkedItem
|
| PURPOSE: To get the address of the first unmarked item in a
|          list.
|
| DESCRIPTION: Returns address of unmarked item or 0 if none
|              found.
|
| EXAMPLE:  AnItem = FindFirstUnMarkedItem(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 12.11.91 by Lee Malone
|          12.14.91 error: loop termination flag not dropped
|          02.08.93 converted from FindFirstUnMarkedItem in
|                   list.txt
|          11.19.93 simplified logic
------------------------------------------------------------*/
AddressOfItem
FindFirstUnMarkedItem(AddressOfList AList)
{
    AddressOfItem    UnMarkedItem;

    PushTheListAndItem();

    TheList = AList;
    UnMarkedItem = (AddressOfItem) 0;

    ToFirstItem();

    while(TheItem)
    {
        if( !IsItemMarked(TheItem) )
        {
            UnMarkedItem = TheItem;
            break;
        }
        ToNextItem();
    }

    PullTheListAndItem();

    return(UnMarkedItem);
}

/*------------------------------------------------------------
| NAME: FindIndexOfFirstMarkedItem
|
| PURPOSE: To get the item index of the first marked item in
| a list.
|
| DESCRIPTION: The first item of the list has an index of 0,
| the next one is 1 and so on.
|
| EXAMPLE:  ItemIndex = FindIndexOfFirstMarkedItem(AList);
|
| NOTE:
|
| ASSUMES: At least one item is marked in the list.
|
| HISTORY: 10.18.91 by Lee Malone
|          02.08.93 converted from list.txt
------------------------------------------------------------*/
Quad
FindIndexOfFirstMarkedItem(AddressOfList AList)
{
    Quad    IndexOfMarkedItem;

    PushTheListAndItem();

    TheList = AList;

    ToFirstItem();

    IndexOfMarkedItem = 0;

    while(!IsItemMarked(TheItem))
    {
        IndexOfMarkedItem++;
        ToNextItem();
    }

    PullTheListAndItem();
    return(IndexOfMarkedItem);
}

/*------------------------------------------------------------
| NAME: FindNextMatchingItem
|
| PURPOSE: To find the next item in a list matching the search
|          string.
|
| DESCRIPTION: Returns pointer to the item found, else 0
| Expects starting item, data field offset, width and pointer
| to value to match. Starts testing for a match on the item
| AFTER the one supplied.
|
|     To be used in conjunction with "FindFirstMatchingItem".
|
| EXAMPLE:
|
|  SearchValue          = (AddressOfByte) "John Galt";
|  SearchKeyFieldOffset = 0;
|  SearchFieldWidth        = CountString(SearchPattern);
|
|  MatchingItem = FindFirstMatchingItem( NameList,
|                                         SearchKeyFieldOffset,
|                                         SearchFieldWidth,
|                                         SearchValue );
|
|  NextMatchItem = FindNextMatchingItem( NameList,
|                                        MatchingItem,
|                                         SearchKeyFieldOffset,
|                                         SearchFieldWidth,
|                                         SearchValue );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 10.23.89 by Lee Malone
|
------------------------------------------------------------*/
AddressOfItem
FindNextMatchingItem( AddressOfList AList,
                      AddressOfItem AnItem,
                      Pair             FieldOffset,
                      Pair            FieldWidth,
                      AddressOfByte SearchValue )
{
     AddressOfItem    Result;

    Result = 0;

    /* Return if no items in the list. */
    if( !IsAnyItemsInList(AList) ) return(Result);

    PushTheListAndItem();

    TheList = AList;
    TheItem = AnItem;

    ToNextItem();

    while( !IsItemLast(TheItem)  )
    {
        if(IsTheDataMatching(FieldOffset, FieldWidth, SearchValue))
            break;
        ToNextItem();
    }

    if( IsTheDataMatching(FieldOffset, FieldWidth, SearchValue) )
    {
        Result = TheItem;
     }

    PullTheListAndItem();

    return( Result );
}

/*------------------------------------------------------------
| NAME: FindPlaceInOrderedList
|
| PURPOSE: To find the item before which the data is to be
|          inserted (data = or < the insertion item's data).
|
| DESCRIPTION: Returns pointer to the item found, else 0 if
| item should be appended to the end of the list.
|
| EXAMPLE: AnItem = FindPlaceInOrderedList(NameList,
|                       (AddressOfByte) "Ken Dannager",
|                       CompareStrings);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 09.06.89 by Lee Malone
|          11.21.93 simplified logic
|
------------------------------------------------------------*/
AddressOfItem
FindPlaceInOrderedList( AddressOfList AList,
                        AddressOfByte SomeData,
    AddressOfComparisonProcedure ComparisonProcedure )
{
    AddressOfItem    AnItem;
    Comparison        Result;

    AnItem = (AddressOfItem) 0;

    if(!IsAnyItemsInList(AList)) return(AnItem);

    PushTheListAndItem();

    TheList = AList;
    ToFirstItem();

    while(TheItem)
    {
        Result = (*ComparisonProcedure)
                    (TheDataAddress, SomeData);

        /*
         * If the current item is of higher order than
         * the data supplied then exit the loop.
         */
        if(Result > 0) break;

        ToNextItem();
    }

    AnItem = TheItem;

    PullTheListAndItem();

    return(AnItem);
}

/*------------------------------------------------------------
| NAME: FindPlaceInOrderedDirectAccessTable
|
| PURPOSE: To find the entry holding the address of the item
|          before which the data is to be inserted; data = or
|          < the insertion item's data.
|
| DESCRIPTION: Returns address of the table entry found,
|              else 0 if it should be appended to the end
|              of the table.
|
| EXAMPLE: AnItemEntry =
|            FindPlaceInOrderedDirectAccessTable(
|                       NameTable,
|                       CountOfNamesInTable,
|                       (AddressOfByte) "Ken Dannager",
|                       CompareStrings);
|
| NOTE: Uses fast binary search algorithm.
|
| ASSUMES:
|
| HISTORY: 09.14.89 by Lee Malone
|          11.21.93 simplified logic
|
------------------------------------------------------------*/
AddressOfAddressOfItem
FindPlaceInOrderedDirectAccessTable(
    AddressOfAddressOfItem       ATable,
    Quad                         ACount,
    AddressOfByte                SomeData,
    AddressOfComparisonProcedure ComparisonProcedure )
{
    AddressOfAddressOfItem    Result;
    SignedQuad                Hi, Lo, Mid;
    Comparison                Cond;

    Result = 0;

    if(ACount <= 0) return(Result);

    /* binary search; ATable[] must be in ascending order */
    Lo = 0;
    Hi = (SignedQuad) ACount - 1;

    while( Lo <= Hi )
    {
        Mid = (Hi + Lo) >> 1; /* (Hi+Lo)/2 */

        Cond = (*ComparisonProcedure)
                  (SomeData, GetItemDataAddress(ATable[Mid]) );

        if( Cond == 0 )
        {
            Result = &ATable[Mid];  /* exact match */
            return(Result);
        }

        if( Cond < 0 )
        {
            Hi = Mid - 1;
        }
        else
        {
            Lo = Mid + 1;
        }
    }

    if( Lo == ACount ) return(Result); /* beyond table */

    Result = &ATable[Lo];        /* higher order entry */

    return(Result);
}

/*------------------------------------------------------------
| NAME: InsertDataAfterItemInList
|
| PURPOSE: To insert a data address into a new item that is
| inserted after a item in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  AnItem = InsertDataAfterItemInList(AList,
|                                              ItemBefore,
|                                              DataToInsert);
|
| NOTE:
|
| ASSUMES:
|
| NOTE: Returns address of the created item.
|
| HISTORY:    01.09.88 by Lee Malone
|
------------------------------------------------------------*/
AddressOfItem
InsertDataAfterItemInList(AddressOfList AList,
                          AddressOfItem AnItem,
                          AddressOfByte AddressOfData)
{
    AddressOfItem NewItem;

    NewItem = CreateItemForData(AddressOfData);
    InsertItemAfterItemInList(AList,AnItem,NewItem);
    return(NewItem);
}

/*------------------------------------------------------------
| NAME: InsertDataBeforeItemInList
|
| PURPOSE: To insert a data address into a new item that is
| inserted before a item in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  AnItem = InsertDataBeforeItemInList(AList,
|                                              ItemAfter,
|                                              DataToInsert);
|
| NOTE:
|
| ASSUMES:
|
| NOTE: Returns address of the created item.
|
| HISTORY:    01.09.88 by Lee Malone
|
------------------------------------------------------------*/
AddressOfItem
InsertDataBeforeItemInList(AddressOfList AList,
                           AddressOfItem AnItem,
                           AddressOfByte AddressOfData)
{
    AddressOfItem NewItem;

    NewItem = CreateItemForData(AddressOfData);
    InsertItemBeforeItemInList(AList,AnItem,NewItem);
    return(NewItem);
}

/*------------------------------------------------------------
| NAME: InsertDataFirstInList
|
| PURPOSE: To insert the given data address into a new item
| that is inserted first in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  AnItem = InsertDataFirstInList(AList,
|                                          DataToInsert);
|
| NOTE:
|
| ASSUMES:
|
| NOTE: Returns address of the created item.
|
| HISTORY:    01.06.88 by Lee Malone
|
------------------------------------------------------------*/
AddressOfItem
InsertDataFirstInList(AddressOfList AList,
                      AddressOfByte DataToInsert)
{
    AddressOfItem AnItem;

    AnItem = CreateItemForData(DataToInsert);
    InsertItemFirstInList(AList,AnItem);
    return(AnItem);
}

/*------------------------------------------------------------
| NAME: InsertDataInOrderedList
|
| PURPOSE: To insert the given data into an ordered list.
|
| DESCRIPTION: The given comparison procedure is the same
| one used to sort the list in order.
|
| EXAMPLE:  NewItem = InsertDataInOrderedList(
|                            NameList,
|                            "Francisco d'Anconia",
|                            CompareStrings);
|
| NOTE:
|
| ASSUMES:
|
| NOTE: Returns address of the created item.
|
| HISTORY: 09.06.89 by Lee Malone
|
------------------------------------------------------------*/
AddressOfItem
InsertDataInOrderedList(AddressOfList AList,
                        AddressOfByte SomeData,
    AddressOfComparisonProcedure ComparisonProcedure)
{
    AddressOfItem     AnItem;
    AddressOfItem    InsertionItem;


    InsertionItem  = FindPlaceInOrderedList(
                        AList,
                        SomeData,
                        ComparisonProcedure );

    AnItem = InsertDataBeforeItemInList(
                        AList,
                        InsertionItem,
                        SomeData );

    return( AnItem );
}

/*------------------------------------------------------------
| NAME: InsertDataLastInList
|
| PURPOSE: To insert the given data address into a new item
| that is inserted last in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  NewItem = InsertDataLasInList(AList, SomeData);
|
| NOTE:
|
| ASSUMES:
|
| NOTE: Returns address of the created item.
|
| HISTORY: 01.09.88 by Lee Malone
|
------------------------------------------------------------*/
AddressOfItem
InsertDataLastInList(AddressOfList AList,
                     AddressOfByte SomeData)
{
    AddressOfItem AnItem;

    AnItem = CreateItemForData(SomeData);
    InsertItemLastInList(AList,AnItem);

    return(AnItem);
}

/*------------------------------------------------------------
| NAME: InsertItemAfterItemInList
|
| PURPOSE: To insert an item after another item in a list.
|
| DESCRIPTION: If the item to preceed the one being inserted
| is '0', then insert the item as first in the list.
|
|
| EXAMPLE:  InsertItemAfterItemInList(AList, ItemBefore,
|                                      ItemToInsert);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.09.88 by Lee Malone
|          11.21.93 if 'ItemBefore' == 0 condition added
|
------------------------------------------------------------*/
Nothing
InsertItemAfterItemInList(AddressOfList AList,
                          AddressOfItem ItemBefore,
                          AddressOfItem ItemToInsert)
{
    AddressOfItem NextItem;

    if(!ItemBefore)
    {
        InsertItemFirstInList(AList,ItemToInsert);
        return;
    }

    if(IsItemLast(ItemBefore))
    {
        InsertItemLastInList(AList,ItemToInsert);
    }
    else
    {
        NextItem = GetNextItem(ItemBefore);
        PutPriorItem(ItemToInsert,ItemBefore);
        PutNextItem(ItemBefore,ItemToInsert);
        PutNextItem(ItemToInsert,NextItem);
        PutPriorItem(NextItem,ItemToInsert);
        AddToListItemCount(AList,1);
    }
}

/*------------------------------------------------------------
| NAME: InsertItemBeforeItemInList
|
| PURPOSE: To insert an item before an item in a list.
|
| DESCRIPTION: If the item to follow the one being inserted
| is '0', then insert the item as last in the list.
|
| EXAMPLE:  InsertItemBeforeItemInList(AList, ItemAfter,
|                                       ItemToInsert);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.09.88 by Lee Malone
|          11.21.93 if 'ItemAfter' == 0 condition added
|
------------------------------------------------------------*/
Nothing
InsertItemBeforeItemInList(AddressOfList AList,
                           AddressOfItem ItemAfter,
                           AddressOfItem ItemToInsert)
{
    AddressOfItem PriorItem;

    if(!ItemAfter)
    {
        InsertItemLastInList(AList,ItemToInsert);
        return;
    }

    if(IsItemFirst(ItemAfter))
    {
        InsertItemFirstInList(AList,ItemToInsert);
    }
    else
    {
        PriorItem = GetPriorItem(ItemAfter);
        PutPriorItem(ItemToInsert,PriorItem);
        PutNextItem(PriorItem,ItemToInsert);
        PutNextItem(ItemToInsert,ItemAfter);
        PutPriorItem(ItemAfter,ItemToInsert);
        AddToListItemCount(AList,1);
    }
}

/*------------------------------------------------------------
| NAME: InsertItemFirstInList
|
| PURPOSE: To insert the given extracted item as the first
|          item in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  InsertItemFirstInList(AList, ItemToInsert);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.09.88 by Lee Malone
|
------------------------------------------------------------*/
Nothing
InsertItemFirstInList(AddressOfList AList,
                      AddressOfItem AnItem)
{

    AddressOfItem FirstItem;

    MarkItemAsFirst(AnItem);

    if(IsAnyItemsInList(AList))
    {
        FirstItem = GetFirstItemOfList(AList);
        PutNextItem(AnItem,FirstItem);
        PutPriorItem(FirstItem,AnItem);
    }
    else
    {
        MarkItemAsLast(AnItem);
        PutLastItemOfList(AList,AnItem);
    }
    AddToListItemCount(AList,1);
    PutFirstItemOfList(AList,AnItem);
}

/*------------------------------------------------------------
| NAME: InsertItemLastInList
|
| PURPOSE: To append the given extracted item to a list.
|
| DESCRIPTION:
|
| EXAMPLE:  InsertItemLastInList(AList, ItemToInsert);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.09.88 by Lee Malone
|
------------------------------------------------------------*/
Nothing
InsertItemLastInList(AddressOfList AList,
                     AddressOfItem AnItem)
{

    AddressOfItem LastItem;

    MarkItemAsLast(AnItem);

    if(IsAnyItemsInList(AList))
    {
        LastItem = GetLastItemOfList(AList);
        PutPriorItem(AnItem,LastItem);
        PutNextItem(LastItem,AnItem);
    }
    else
    {
        MarkItemAsFirst(AnItem);
        PutFirstItemOfList(AList,AnItem);
    }
    AddToListItemCount(AList,1);
    PutLastItemOfList(AList,AnItem);
}

/*------------------------------------------------------------
| NAME: IsAnyItemMarkedInList
|
| PURPOSE: To tell if any item is marked in a list.
|
| DESCRIPTION:  Returns non-zero if any item is marked.
|
| EXAMPLE:  Result = IsAnyItemMarkedInList( AList );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 10.18.91 by Lee Malone
|          12.19.91 fixed to handle empty lists
|          02.08.93 converted from list.txt
|          11.19.93 simplified logic
------------------------------------------------------------*/
Truth
IsAnyItemMarkedInList(AddressOfList AList)
{
    Truth    Result;

    Result = False;

    PushTheListAndItem();

    TheList = AList;

    ToFirstItem();

    while(TheItem)
    {
        if( IsItemMarked(TheItem) )
        {
            Result = True;
            break;
        }
        ToNextItem();
    }

    PullTheListAndItem();

    return(Result);
}

/*------------------------------------------------------------
| NAME: IsAnyItemsInList
|
| PURPOSE: To tell if list has existing items.
|
| DESCRIPTION:
|
| EXAMPLE:  Result = IsAnyItemsInList( AList );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.05.88 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsAnyItemsInList(AddressOfList AList)
{
    return( GetListItemCount(AList) );
}

/*------------------------------------------------------------
| NAME: IsItemAlone
|
| PURPOSE: To tell if a item is the only one in a list.
|
| DESCRIPTION:If both next and prior are 0, and therefore equal,
| then this is the only item.
|
| EXAMPLE:  if( IsItemAlone(AnItem) ) return(True);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.88 by Lee Malone
|          07.12.89 revised
|
------------------------------------------------------------*/
Truth
IsItemAlone(AddressOfItem AnItem)
{
    return( GetPriorItem(AnItem) == GetNextItem(AnItem)  );
}

/*------------------------------------------------------------
| NAME: IsItemCreationPossible
|
| PURPOSE: To tell if a list can be created.
|
| DESCRIPTION:
|
| EXAMPLE:  IsItemCreationPossible();
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 07.19.89 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsItemCreationPossible()
{
    return( CountOfFreeItems );
}

/*------------------------------------------------------------
| NAME: IsItemFirst
|
| PURPOSE: To tell if a item is first in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  if( IsItemFirst(AnItem) ) return(True);
|
| NOTE:
|
| ASSUMES:
|
| NOTE: If AddressOfPriorItem is 0, then item is first
|
| HISTORY: 01.04.88 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsItemFirst(AddressOfItem AnItem)
{
    return(!GetPriorItem(AnItem));
}

/*------------------------------------------------------------
| NAME: IsItemLast
|
| PURPOSE: To tell if a item is last in a list.
|
| DESCRIPTION: If AddressOfNextItem is 0 then it is the last
|              item.
|
| EXAMPLE:  if( IsItemLast(AnItem) ) return(True);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.88 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsItemLast(AddressOfItem AnItem)
{
    return(!GetNextItem(AnItem));
}

/*------------------------------------------------------------
| NAME: IsItemMarked
|
| PURPOSE: To tell if a item is marked.
|
| DESCRIPTION:
|
| EXAMPLE:  if( IsItemMarked(AnItem) ) UnMarkItem(AnItem);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 07.12.89 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsItemMarked(AddressOfItem AnItem)
{
    return(GetItemMark(AnItem) & Marked);
}

/*------------------------------------------------------------
| NAME: IsListCreationPossible
|
| PURPOSE: To tell if a list can be created.
|
| DESCRIPTION:
|
| EXAMPLE:  IsListCreationPossible();
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 07.19.89 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsListCreationPossible()
{
    return( CountOfFreeLists );
}

/*------------------------------------------------------------
| NAME: IsListMarked
|
| PURPOSE: To tell if list is marked.
|
| DESCRIPTION:
|
| EXAMPLE:  if( IsListMarked(AList) ) UnMarkList(AList);
|
| NOTE:
|
| ASSUMES:
|
| NOTE:
|
| HISTORY: 07.09.88 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsListMarked(AddressOfList ListAddress)
{
    return(GetListMark(ListAddress) & Marked);
}

/*------------------------------------------------------------
| NAME: IsTheDataMatching
|
| PURPOSE: To tell if a field in the data of the current
|          item matches a given test value.
|
| DESCRIPTION:
|
| EXAMPLE:
|
|    TheItem = SomeNameItem;
|
|    Result =  IsTheDataMatching((Pair) 0,
|                                (Pair) 4,
|                                (AddressOfByte) "John" )
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 10.23.89 by Lee Malone
|
------------------------------------------------------------*/
Truth
IsTheDataMatching(Pair          FieldOffset,
                  Pair          FieldWidth,
                  AddressOfByte DataToMatch )
{
    AddressOfByte    FieldAddress;

    FieldAddress = TheDataAddress;

    return( IsMatchingBytes( (AddressOfByte)
                             &FieldAddress[FieldOffset],
                             DataToMatch,
                             (Quad) FieldWidth ) );
}

/*------------------------------------------------------------
| NAME: JoinLists
|
| PURPOSE: To join two lists together to form one list.
|
| DESCRIPTION: The items of the follower list, are appended
| to the leader list, and then the empty follower list is
| deleted.
|
| EXAMPLE:
|
|     JoinLists(ListA, ListB);
|
|     will result in the items from listB being tacked onto
|     the end of ListA and then the list record for ListB
|     will be deleted.
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 12.11.91 by Lee Malone
|          10.29.93 ported from Focus project
------------------------------------------------------------*/
Nothing
JoinLists ( AddressOfList LeaderList,
            AddressOfList FollowerList)
{
    AddressOfItem    LastItemOfLeader;
    AddressOfItem    FirstItemOfFollower;
    Pair            NewMark;

    /* If the FollowerList has no items then return. */
    if( !IsAnyItemsInList(FollowerList) ) return;

    LastItemOfLeader    = GetLastItemOfList(LeaderList);
    FirstItemOfFollower = GetFirstItemOfList(FollowerList);

    /* If the LeaderList has existing items */
    if( IsAnyItemsInList(LeaderList) )
    {

        /*
         * Link the next link of the leader list
         * to the beginning of the follower.
         */
        PutNextItem( LastItemOfLeader, FirstItemOfFollower );

        /*
         * Link the prior link of the follower list
         * to the end of the leader list.
         */
        PutPriorItem( FirstItemOfFollower, LastItemOfLeader );
    }
    else /* LeaderList is empty. */
    {
        /*
         * Set the first item pointer in the
         * destination list from the source list
         */
        PutFirstItemOfList(LeaderList, FirstItemOfFollower );
    }

    /*
     * Set the last item pointer in the
     * destination list from the source list
     */
    PutLastItemOfList( LeaderList, GetLastItemOfList(FollowerList));
    /*
     * Sum the counts of the two lists.
     */
    AddToListItemCount(LeaderList,
                       GetListItemCount(FollowerList));
    /*
     * OR the marks of the two lists
     */
    NewMark = GetListMark(LeaderList) | GetListMark(FollowerList);
    PutListMark(LeaderList,NewMark);

    /*
     * Clear the list count & pointers for the
     * follower list.
     */
    MarkListAsEmpty(FollowerList);

    /* Return the list record to the list pool for reuse. */
    DeleteList(FollowerList);
}

/*------------------------------------------------------------
| NAME: MarkItem
|
| PURPOSE: To mark a item.
|
| DESCRIPTION:
|
| EXAMPLE:  MarkItem(AnItem);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 07.18.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
MarkItem(AddressOfItem AnItem)
{
    PutItemMark(AnItem, GetItemMark(AnItem)|Marked);
}

/*------------------------------------------------------------
| NAME: MarkItemAsFirst
|
| PURPOSE: To mark a item as first in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  MarkItemAsFirst(AnItem);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.09.88 by Lee Malone
|          07.10.89 new structure revision
|
------------------------------------------------------------*/
Nothing
MarkItemAsFirst(AddressOfItem AnItem)
{
    PutPriorItem(AnItem,(AddressOfItem) 0);
}

/*------------------------------------------------------------
| NAME: MarkItemAsLast
|
| PURPOSE: To mark a item as last in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  MarkItemAsLast(AnItem);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.09.88 by Lee Malone
|          07.10.89 new structure revision
|
------------------------------------------------------------*/
Nothing
MarkItemAsLast(AddressOfItem AnItem)
{
    PutNextItem(AnItem,0);
}

/*------------------------------------------------------------
| NAME: MarkList
|
| PURPOSE: To mark a list.
|
| DESCRIPTION:
|
| EXAMPLE:  MarkList( AList );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 07.19.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
MarkList(AddressOfList AList)
{
    PutListMark(AList, GetListMark(AList) | Marked );
}

/*------------------------------------------------------------
| NAME: MarkListAsEmpty
|
| PURPOSE: To mark a list as having no items.
|
| DESCRIPTION:
|
| EXAMPLE:  MarkListAsEmpty( AList );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
MarkListAsEmpty(AddressOfList AList)
{
    PutListItemCount(AList,(Quad) 0);
    PutFirstItemOfList(AList,(AddressOfItem) 0);
    PutLastItemOfList(AList,(AddressOfItem) 0);
}

/*------------------------------------------------------------
| NAME: OutputListOfStrings
|
| PURPOSE: To output strings attached to a list.
|
| DESCRIPTION: Each string is placed on a separate line.
| A blank line is printed after the list.
|
| EXAMPLE:  OutputListOfStrings( MyList, OutputFile );
|
| NOTE:
|
| ASSUMES: Each string is able to fit on a single line.
|
| HISTORY: 01.13.88 by Lee Malone
|          02.08.93 removed item count control in favor of
|                    TheItem being non-0.
|          11.08.93 added explicit stream parameter
------------------------------------------------------------*/
Nothing
OutputListOfStrings(AddressOfList AList,
                    FILE *OutputStream)
{
    PushTheListAndItem();

    TheList = AList;

    ToFirstItem();

    while(TheItem)
    {
        fprintf(OutputStream,"%s\n",
            (AddressOfString)TheDataAddress);
        ToNextItem();
    }

    fprintf(OutputStream,"\n");

    PullTheListAndItem();
}

/*------------------------------------------------------------
| NAME: OutputListSystemStatus
|
| PURPOSE: To report on list system status.
|
| DESCRIPTION:
|
| EXAMPLE:  OutputListSystemStatus(OutputFile);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 11.26.91 by Lee Malone
|          11.01.93 extended
|          11.08.93 added 'OutputStream' parameter
------------------------------------------------------------*/
Nothing
OutputListSystemStatus(FILE *OutputStream)
{
    AddressOfString    MarkString;

    fprintf(OutputStream,"\n");
    fprintf(OutputStream,"List System Status:\n");
    fprintf(OutputStream,"    TheListSystemIsSetUp...%d\n\n",
                         TheListSystemIsSetUp);

    fprintf(OutputStream,"    ListsInUse.............%ld\n",
                         (MaxCountOfLists-CountOfFreeLists));
    fprintf(OutputStream,"    ItemsInUse.............%ld\n\n",
                                  (MaxCountOfItems-CountOfFreeItems));
    fprintf(OutputStream,"    FreeLists..............%ld\n",
                                  CountOfFreeLists);
    fprintf(OutputStream,"    FreeItems..............%ld\n\n",
                                  CountOfFreeItems);

    fprintf(OutputStream,"    TheList................%lx\n",TheList);
    if(TheList)
    {
          fprintf(OutputStream,"        TheFirstItem.......%lx\n",
                                            TheFirstItem);
          fprintf(OutputStream,"        TheLastItem........%lx\n",
                                            TheLastItem);
          MarkString = "UnMarked";
          if(IsListMarked(TheList)) MarkString = "Marked";
          fprintf(OutputStream,"        TheListMark........%s\n",
                                               MarkString);
          fprintf(OutputStream,"        TheItemCount.......%ld\n\n",
                                            TheItemCount);
    }

    fprintf(OutputStream,"    TheItem................%lx\n",TheItem);
    if(TheItem)
    {
        fprintf(OutputStream,"        ThePriorItem.......%lx\n",
                                            ThePriorItem);
        fprintf(OutputStream,"        TheNextItem........%lx\n",
                                            TheNextItem);
        MarkString = "UnMarked";
        if(IsItemMarked(TheItem)) MarkString = "Marked";
        fprintf(OutputStream,"        TheItemMark........%s\n",
                                            MarkString);
        fprintf(OutputStream,"        TheDataAddress.....%lx\n",
                                            TheDataAddress);
    }
}

/*------------------------------------------------------------
| NAME: PullTheItem
|
| PURPOSE: To pull TheItem from TheListStack.
|
| DESCRIPTION:
|
| EXAMPLE:  PullTheItem();
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
PullTheItem()
{
    TheItem = (AddressOfItem)
              TheListStack[TheListStackIndex--];
}

/*------------------------------------------------------------
| NAME: PullTheList
|
| PURPOSE: To pull TheList from TheListStack.
|
| DESCRIPTION:
|
| EXAMPLE:  PullTheList();
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
PullTheList()
{
    TheList = (AddressOfList)
              TheListStack[TheListStackIndex--];
}

/*------------------------------------------------------------
| NAME: PullTheListAndItem
|
| PURPOSE: To pull The Item and TheList from TheListStack.
|
| DESCRIPTION:
|
| EXAMPLE:  PullTheListAndItem();
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
PullTheListAndItem()
{
    PullTheItem();
    PullTheList();
}

/*------------------------------------------------------------
| NAME: PushTheItem
|
| PURPOSE: To save TheItem on TheListStack.
|
| DESCRIPTION:
|
| EXAMPLE:  PushTheItem()
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
PushTheItem()
{
    TheListStack[++TheListStackIndex] = (Quad) TheItem;
}

/*------------------------------------------------------------
| NAME: PushTheList
|
| PURPOSE: To save TheList on TheListStack.
|
| DESCRIPTION:
|
| EXAMPLE:  PushTheList()
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
PushTheList()
{
    TheListStack[++TheListStackIndex] = (Quad) TheList;
}

/*------------------------------------------------------------
| NAME: PushTheListAndItem
|
| PURPOSE: To save TheList and TheItem on TheListStack.
|
| DESCRIPTION:
|
| EXAMPLE:  PushTheListAndItem()
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
PushTheListAndItem()
{
    PushTheList();
    PushTheItem();
}

/*------------------------------------------------------------
| NAME: ReorderListToMatchDirectAccessTable
|
| PURPOSE: To make the order of items in a list conform to
| the items in a DirectAccessTable.
|
| DESCRIPTION: After reordering a list via a direct access
| table it may be necessary to make the original list conform
| to the new ordering: this procedure does that.
|
| EXAMPLE:  ReorderListToMatchDirectAccessTable(
|                    NameList,
|                   AlphaNameTable);
|
| NOTE:
|
| ASSUMES: All items are contained in both the list
|          and the direct access table.
|
| HISTORY: 09.12.89 by Lee Malone
|          10.28.93 revised for speed.
|
------------------------------------------------------------*/
Nothing
ReorderListToMatchDirectAccessTable( AddressOfList AList,
                                     AddressOfAddressOfItem Table )
{
    Quad            CountOfItems;
    Quad            IndexOfLastItem;
    Quad            Entry;
    AddressOfItem    PriorItem;
    AddressOfItem    NextItem;

    CountOfItems = GetListItemCount(AList);

    if( CountOfItems < 2) return;

    IndexOfLastItem = CountOfItems - 1;

    PushTheListAndItem();

    TheList = AList;

    /* Adjust the list record first. */
    TheFirstItem = Table[0];
    TheLastItem  = Table[IndexOfLastItem];

    /* Adjust the item pointers for all items but the last. */
    PriorItem = 0;

    for( Entry = 0; Entry < IndexOfLastItem; Entry++ )
    {
        TheItem  = Table[Entry];
        NextItem = Table[Entry+1];

        ThePriorItem = PriorItem;
        TheNextItem  = NextItem;

        PriorItem = TheItem;
    }

    /* Adjust the last item. */
    TheItem      = Table[IndexOfLastItem];
    ThePriorItem = Table[IndexOfLastItem-1];
    TheNextItem  = 0;

    PullTheListAndItem();
}


/*------------------------------------------------------------
| NAME: ReverseList
|
| PURPOSE: To reverse the ordering of items in a list.
|
| DESCRIPTION:
|
| EXAMPLE:  ReverseList(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 11.02.93 by Lee Malone
|
------------------------------------------------------------*/
Nothing
ReverseList(AddressOfList AList)
{
    AddressOfItem    NextItem;
    AddressOfItem    FirstItem;

    PushTheListAndItem();

    TheList = AList;
    ToFirstItem();

    while(TheItem)
    {
        /* Exchange the next and prior item addresses. */
        NextItem     = TheNextItem;
        TheNextItem  = ThePriorItem;
        ThePriorItem = NextItem;

        TheItem = NextItem;
    }

    /* Exchange the endpoint addresses in the list record. */
    FirstItem    = TheFirstItem;
    TheFirstItem = TheLastItem;
    TheLastItem  = FirstItem;

    PullTheListAndItem();
}

/*------------------------------------------------------------
| NAME: SetUpTheListSystem
|
| PURPOSE: To set up the list system for use.
|
| DESCRIPTION: Allocates memory space for subsequent use
| as list and item records.  This procedure sets an upper
| limit on how many list or item records can be created.
|
| All available list records are linked together using their
| 'AddressOfFirstItem' fields and placed into the free list.
| A count of lists in the free list is maintained. There
| is no terminating 0 for the list: use 'CountOfFreeLists'
| instead to tell if the list is empty.
|
| All available item records are linked together using their
| 'AddressOfNextItem' fields and placed into the free item
| list. A count of items in the free list is maintained.
| There is no terminating 0 for the list: use
| 'CountOfFreeItems' instead to tell if the list is empty.
|
| EXAMPLE:  SetUpTheListSystem((Quad) HowManyLists,
|                              (Quad) HowManyItems);
|
| NOTE: This procedure must be executed prior to running
|       any other procedure in the list system.
|
| ASSUMES:
|
| HISTORY: 03.09.89 by Lee Malone
|          07.09.89 Changed to pre-allocate all possible
|                   lists and items.
|          07.19.89 added free list
|
------------------------------------------------------------*/
Nothing
SetUpTheListSystem(Quad MaximumLists, Quad MaximumItems)
{
    Quad SizeOfListSpace, SizeOfItemSpace,i;

    if( !TheListSystemIsSetUp )
    {
        TheListStackIndex = 0;

        MaxCountOfLists = MaximumLists;
        MaxCountOfItems = MaximumItems;

        SizeOfListSpace = MaxCountOfLists*sizeof(List);
        SizeOfItemSpace = MaxCountOfItems*sizeof(Item);

        ListSpace = AllocateMemory(SizeOfListSpace);
        if(ListSpace == 0)
        {
            printf("Error: Unable to allocate list space.\n");
            exit(1);
        }

        ItemSpace = AllocateMemory(SizeOfItemSpace);
        if(ItemSpace == 0)
        {
            printf("Error: Unable to allocate item space.\n");
            exit(1);
        }

        CountOfFreeItems = MaxCountOfItems;
        CountOfFreeLists = MaxCountOfLists;

        FirstFreeList = ListSpace;
        FirstFreeItem = ItemSpace;

        /* Use the 'AddressOfFirstItem' field to link all free
           list records together.
        */
        for( i = 0; i < MaxCountOfLists ; i++ )
        {
            ListSpace[i].AddressOfFirstItem =
            (AddressOfItem) &ListSpace[i+1];
        }

        /* Use the 'AddressOfNextItem' field to link all free
           item records together.
        */
        for( i = 0; i < MaxCountOfItems ; i++ )
        {
            ItemSpace[i].AddressOfNextItem =
            (AddressOfItem) &ItemSpace[i+1];
        }
    }
    TheListSystemIsSetUp++;
}

/*------------------------------------------------------------
| NAME: SortDirectAccessTable
|
| PURPOSE: To sort a direct access table in ascending order.
|
| DESCRIPTION: Expects the address of a direct access table,
| a count of entries in the table, and the address of the
| comparison procedure to be used.
|
| Uses fast Heap Sort procedure.
|
| A direct access table is an array of item record addresses.
|
| EXAMPLE:
|
| SortDirectAccessTable( ATable,
|                        EntryCount,
|                        CompareStrings );
|
| NOTE: Especially well suited to long tables as the run time
| is proportional to Nlog2N as a worst case, eg. a 256 element
| list would take time proportional to 256*8 = 2048 vs.
| N*N or 64K for the bubble sort.
|
| ASSUMES:
|
| NOTE: See "Numerical Recipes, The Art of Scientific
|        Computing", page 229, for complete explanation.
|
| HISTORY: 09.12.89 by Lee Malone
|          12.22.91 revised to use Heap Sort algorithm.
|          11.02.93 ported from Focus.
|
------------------------------------------------------------*/
Nothing
SortDirectAccessTable(
    AddressOfAddressOfItem          ATable,
    Quad                            TableCount,
    AddressOfComparisonProcedure ComparisonProcedure)
{
    AddressOfByte  AData;
    AddressOfByte  BData;
    AddressOfItem  EntryBeingMoved;
    Comparison       ComparisonResult;
    Quad           HeapIndexL;
    Quad           HeapIndexIR;
    Quad           HeapIndexI;
    Quad           HeapIndexJ;

    if(TableCount < 2) return;

    HeapIndexL  = (TableCount >> 1) + 1;
    HeapIndexIR = TableCount;

    while(1)
    {
        if(HeapIndexL > 1)
        {
            HeapIndexL--;
            EntryBeingMoved = ATable[HeapIndexL-1];
        }
        else
        {
            EntryBeingMoved = ATable[HeapIndexIR-1];
            ATable[HeapIndexIR-1] = ATable[0];
            HeapIndexIR--;
            if( HeapIndexIR == 1 ) /* at the end */
            {
                ATable[0] = EntryBeingMoved;
                   return;
            }
        }

        HeapIndexI = HeapIndexL;
        HeapIndexJ = HeapIndexL<<1;

        while( HeapIndexJ <= HeapIndexIR )
        {
            if( HeapIndexJ < HeapIndexIR )
            {
                AData = GetItemDataAddress(ATable[HeapIndexJ-1]);
                BData = GetItemDataAddress(ATable[HeapIndexJ]);

                  ComparisonResult  =
                    (*ComparisonProcedure)(AData,BData);

                if( ComparisonResult < 0 )
                {
                    HeapIndexJ++;
                }
            }

            AData = GetItemDataAddress(EntryBeingMoved);
            BData = GetItemDataAddress(ATable[HeapIndexJ-1]);

            ComparisonResult = (*ComparisonProcedure)(AData,BData);

            if( ComparisonResult < 0 )
            {

              ATable[HeapIndexI-1] = ATable[HeapIndexJ-1];
              HeapIndexI = HeapIndexJ;
              HeapIndexJ += HeapIndexJ;
            }
            else
            {
              HeapIndexJ = HeapIndexIR+1;
            }
        }

        ATable[HeapIndexI - 1] = EntryBeingMoved;
    }
}

/*------------------------------------------------------------
| NAME: SortList
|
| PURPOSE: To sort a list in ascending order using a given
| comparison procedure.
|
| DESCRIPTION: Uses one of two algorithms depending on the
| length of the list:
|
| 1. For lists with more items than 'DirectAccessTableThreshold',
|    the list is sorted by way of a direct access table using a
|    HeapSort algorithm.
|
| 2. Shorter lists use a simple, slower bubble sort algorithm.
|
| EXAMPLE:  SortList( ListOfNames, CompareStrings );
|
| NOTE: See 'CompareStrings' for an example of a comparison
| procedure.  Use it as a template for other comparison
| procedures.
|
| ASSUMES:
|
| NOTE:
|
| HISTORY: 11.02.93 by Lee Malone
|
------------------------------------------------------------*/
Nothing
SortList(AddressOfList AList,
         AddressOfComparisonProcedure ComparisonProcedure)
{

    if( GetListItemCount(AList) > DirectAccessTableThreshold )
    {
        SortListViaDirectAccessTable(
            AList,
            ComparisonProcedure);
    }
    else
    {
        SortShortList(AList,ComparisonProcedure);
    }
}

/*------------------------------------------------------------
| NAME: SortListAlphabetically
|
| PURPOSE: To sort a list alphabetically.
|
| DESCRIPTION:
|
| EXAMPLE:  SortListAlphabetically( ListOfNames );
|
| NOTE:
|
| ASSUMES:
|
| NOTE: Case insensitive.
|
| HISTORY: 01.13.89 by Lee Malone
|          11.02.93 revised to call 'SortList'.
|
------------------------------------------------------------*/
Nothing
SortListAlphabetically(AddressOfList AList)
{
    AddressOfComparisonProcedure ComparisonProcedure;

    ComparisonProcedure = (AddressOfComparisonProcedure)
                          CompareStrings;

    SortList(AList,ComparisonProcedure);
}

/*------------------------------------------------------------
| NAME: SortListDescending
|
| PURPOSE: To sort a list in descending order.
|
| DESCRIPTION: Pass the comparison function to be used.
|
|
| EXAMPLE:  SortListDescending( ListOfNames, CompareStrings );
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.11.89 by Lee Malone
|          09.14.89 BackCount added.
|          11.02.93 revised to use 'ReverseList'.
------------------------------------------------------------*/
Nothing
SortListDescending(AddressOfList AList,
    AddressOfComparisonProcedure ComparisonProcedure)
{
    SortList(AList,ComparisonProcedure);
    ReverseList(AList);
}

/*------------------------------------------------------------
| NAME: SortListViaDirectAccessTable
|
| PURPOSE: To sort a list in ascending order by first
| creating a direct access table.
|
| DESCRIPTION: Pass the comparison function to be used. Uses
| fast heap sort algorithm.
| Creates a direct access table, sorts it, conforms list to
| ordering of the table, then discards the table.
|
| Primarily for use with long lists.
|
| EXAMPLE:
|        SortListViaDirectAccessTable( ListOfNames,
|                                      CompareStrings );
| NOTE:
|
| ASSUMES: Enough memory exists for direct access table
|          built by this procedure.
|
| HISTORY: 09.12.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
SortListViaDirectAccessTable( AddressOfList AList,
    AddressOfComparisonProcedure ComparisonProcedure)
{
    AddressOfAddressOfItem     TablePointer;

    TablePointer = BuildDirectAccessTableForList( AList );

    SortDirectAccessTable( TablePointer,
                           GetListItemCount(AList),
                           ComparisonProcedure );

    ReorderListToMatchDirectAccessTable( AList,
                                         TablePointer );

    FreeMemory( TablePointer );
}

/*------------------------------------------------------------
| NAME: SortShortList
|
| PURPOSE: To sort a given list in ascending order using
| a given comparison procedure.
|
| DESCRIPTION: Uses simple but slow bubble sort function.
| Doesn't require any additional storage.
|
| EXAMPLE:  SortShortList( ListOfNames, CompareStrings );
|
| NOTE: Use for short lists only.
|
| ASSUMES:
|
| NOTE:
|
| HISTORY: 01.11.89 by Lee Malone
|          09.14.89 BackCount added.
|
------------------------------------------------------------*/
Nothing
SortShortList(AddressOfList      AList,
    AddressOfComparisonProcedure ComparisonProcedure)
{
    Truth             IsInOrder;
    AddressOfByte   AddressOfDataFromNextItem;
    AddressOfItem   AddressOfNextItem;
    Comparison      ComparisonResult;
    Quad            Repetitions,BackCount;

    if( GetListItemCount(AList) < 2 ) return;

    PushTheListAndItem();

    TheList = AList;

    IsInOrder = 0;

    BackCount = 1;

    while(IsInOrder == 0)
    {
        IsInOrder = 1;
        ToFirstItem();
        Repetitions = TheItemCount - BackCount++;
        while(Repetitions--)
        {
            AddressOfNextItem         = TheNextItem;
            AddressOfDataFromNextItem =
                    GetItemDataAddress(AddressOfNextItem);
            ComparisonResult        =
                (*ComparisonProcedure)
                (TheDataAddress,AddressOfDataFromNextItem);

            if(ComparisonResult > 0)
            {
                ExchangeItems(TheList,TheItem,AddressOfNextItem);
                IsInOrder = 0;
            }
            else
            {
                ToNextItem();
            }
        }
    }
    PullTheListAndItem();
}

/*------------------------------------------------------------
| NAME: ToFirstItem
|
| PURPOSE: To set the current item to be the first item in
|          the current list.
|
| DESCRIPTION:
|
| EXAMPLE:
|          TheList = ListOfNames;
|          ToFirstItem();
|
|          while(TheItem)
|          {
|               ConvertStringToUpperCase(
|                    (AddressOfString)TheDataAddress);
|               ToNextItem();
|          }
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
ToFirstItem()
{
    TheItem = TheFirstItem;
}

/*------------------------------------------------------------
| NAME: ToLastItem
|
| PURPOSE: To set the current item to be the last item in
|          the current list.
|
| DESCRIPTION:
|
| EXAMPLE:
|          TheList = ListOfNames;
|          ToLastItem();
|
|          while(TheItem)
|          {
|               ConvertStringToUpperCase(
|                    (AddressOfString)TheDataAddress);
|                ToPriorItem();
|           }
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
ToLastItem()
{
    TheItem = TheLastItem;
}

/*------------------------------------------------------------
| NAME: ToNextItem
|
| PURPOSE: To set the current item to be the next item in
|          the current list.
|
| DESCRIPTION: A list traversal operation.
|
| EXAMPLE:
|          TheList = ListOfNames;
|          ToFirstItem();
|
|          while(TheItem)
|          {
|               ConvertStringToUpperCase(
|                    (AddressOfString)TheDataAddress);
|                ToNextItem();
|           }
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
ToNextItem()
{
    TheItem = GetNextItem(TheItem);
}

/*------------------------------------------------------------
| NAME: ToPriorItem
|
| PURPOSE: To set a new current item via AddressOfPriorItem
| from TheItem.
|
| DESCRIPTION: A list traversal operation.
|
| EXAMPLE:
|          TheList = ListOfNames;
|          ToLastItem();
|
|          while(TheItem)
|          {
|               ConvertStringToUpperCase(
|                    (AddressOfString)TheDataAddress);
|                ToPriorItem();
|           }
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 01.04.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
ToPriorItem()
{
    TheItem = GetPriorItem(TheItem);
}

/*------------------------------------------------------------
| NAME: UnMarkAllItemsInList
|
| PURPOSE: To clear item marks on all items in a list.
|
| DESCRIPTION:  Item marks may be used to separate some items
| from others in a list, e.g. to show which ones are selected.
|
| EXAMPLE:  UnMarkAllItemsInList(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 10.08.91 by Lee Malone
|          02.08.93 from list.txt
------------------------------------------------------------*/
Nothing
UnMarkAllItemsInList(AddressOfList ListAddress)
{
    PushTheListAndItem();

    TheList = ListAddress;

    ToFirstItem();

    while(TheItem)
    {
        UnMarkItem(TheItem);
        ToNextItem();
    }

    PullTheListAndItem();
}

/*------------------------------------------------------------
| NAME: UnMarkItem
|
| PURPOSE: To unmark a item.
|
| DESCRIPTION:
|
| EXAMPLE:  UnMarkItem(AnItem);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 07.18.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
UnMarkItem(AddressOfItem AnItem)
{
    PutItemMark(AnItem, GetItemMark(AnItem) & ~Marked);
}

/*------------------------------------------------------------
| NAME: UnMarkList
|
| PURPOSE: To unmark a list.
|
| DESCRIPTION:
|
| EXAMPLE:  UnMarkList(AList);
|
| NOTE:
|
| ASSUMES:
|
| HISTORY: 07.19.89 by Lee Malone
|
------------------------------------------------------------*/
Nothing
UnMarkList(AddressOfList AList)
{
    PutListMark(AList, GetListMark(AList) & ~Marked );
}